#define _CRT_SECURE_NO_WARNINGS 1 

#include <stdio.h>
#include <malloc.h>

//线性结构的应用 --- 队列

//定义：
//	一种可以实现“先进先出”的存储结构

//分类：
//	链式队列 -- 用链表实现
//		
//	静态队列 -- 用数组实现
//		静态队列通常都必须是循环队列
//！！！循环队列的讲解：
//		1.静态队列为什么必须是循环队列
// 
//		2.循环队列需要几个参数来确定
//			需要两个参数来确定（front、rear）
//
//		3.循环队列各个参数的含义
//			！两个参数在不同的环境下有不同的含义
//				先牢记，然后慢慢体会：
//				1).队列初始化
//				  front和rear的值都为0
//				2).队列非空
//				  front代表的是队列的第一个元素，rear代表的是队列最后一个有效元素的下一个元素
//				3).队列空
//				  front和rear的值相等，但不一定为0
// 
//		4.循环队列入队伪算法讲解
//			两步完成：
//			1).将值存入rear所代表的的位置
//			2).rear = rear+1;//写法错误！
//			   rear = (rear + 1) % 数组长度;//正确写法
// 
//		5.循环队列出队伪算法讲解
//			front = (front + 1) % 数组长度
//
//		6.如何判断循环队列是否为空
//			如果front和rear的值相等，则该队列就一定为空
//
//		7.如何判断循环队列是否已满
//			两种方式：
//			1).多增加一个标志位标识参数
//			2).少用一个元素[通常使用第2种方式]
//				如果rear和front的值相邻（紧挨），则队列已满
//				if ((rear + 1) % 数组长度 == f)
//				{
//					队列已满
//				}
//				else
//				{
//					队列未满
//				}

//算法：
//	入队
//	出队

//应用：
//	所有和时间有关的操作都与队列有关

typedef struct Queue
{
	int* pBase;
	int front;
	int rear;
}QUEUE, * PQUEUE;

//函数声明
void Init_Queue(PQUEUE);//初始化
bool Is_Empty_Queue(PQUEUE);//判空
bool Is_Full_Queue(PQUEUE);//判满
bool En_Queue(PQUEUE, int);//入队
bool Out_Queue(PQUEUE, int*);//出队
void Traverse_Queue(PQUEUE);//遍历

int main(void)
{
	QUEUE Q;
	int val = 0;

	//初始化
	Init_Queue(&Q);

	//入队
	En_Queue(&Q, 1);
	En_Queue(&Q, 2);
	En_Queue(&Q, 3);
	En_Queue(&Q, 4);
	En_Queue(&Q, 5);
	En_Queue(&Q, 6);
	En_Queue(&Q, 7);
	En_Queue(&Q, 8);
	Traverse_Queue(&Q);//遍历

	//出队
	if (Out_Queue(&Q, &val))
	{
		printf("出队成功！队列出队元素是:>%d\n", val);
	}
	else
	{
		printf("出队失败！\n");
	}
	Traverse_Queue(&Q);

	return 0;
}

//初始化
void Init_Queue(PQUEUE pQ)
{
	pQ->pBase = (int*)malloc(sizeof(int) * 6);
	pQ->front = 0;
	pQ->rear = 0;
}

//判空
bool Is_Empty_Queue(PQUEUE pQ)
{
	if (pQ->front == pQ->rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//判满
bool Is_Full_Queue(PQUEUE pQ)
{
	if ((pQ->rear + 1) % 6 == pQ->front)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//入队
bool En_Queue(PQUEUE pQ, int val)
{
	if (Is_Full_Queue(pQ))
	{
		return false;
	}
	else
	{
		pQ->pBase[pQ->rear] = val;
		pQ->rear = (pQ->rear + 1) % 6;

		return true;
	}
}

//出队
bool Out_Queue(PQUEUE pQ, int *pVal)
{
	if (Is_Empty_Queue(pQ))
	{
		return false;
	}
	else
	{
		*pVal = pQ->pBase[pQ->front];
		pQ->front = (pQ->front + 1) % 6;

		return true;
	}
}

//遍历
void Traverse_Queue(PQUEUE pQ)
{
	int i = pQ->front;

	while (i != pQ->rear)
	{
		printf("%d ", pQ->pBase[i]);
		i = (i + 1) % 6;
	}
	printf("\n");

	return;

}